package com.sise.DP;

/**
 *      63. 不同路径 II
 *
 *      一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
 *      机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
 *      现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
 *      网格中的障碍物和空位置分别用 1 和 0 来表示。
 */
public class _63_uniquePathsWithObstacles {
    public static void main(String[] args) {
        int[][] a = {{0, 0},
                {0, 1},
                {0, 0}};
        uniquePathsWithObstacles_2(a);
    }

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {

        if (obstacleGrid == null || obstacleGrid.length == 0) {
            return 0;
        }

        int row = obstacleGrid.length;      // 行
        int col = obstacleGrid[0].length;   // 列
        int[][] dp = new int[row][col];

        // 这里的处理比较巧妙，假设障碍物在中间 [0,0,1,0]，那么后续的路也走不了，
        // 循环中是通过 && obstacleGrid[i][0] == 0 进行处理，当第一次遇见障碍物为 1 时，处理完就会退出循环，那么后续的数值默认为 0
        for (int i = 0; i < row && obstacleGrid[i][0] == 0; i++) {
            dp[i][0] = 1;
        }
        for (int i = 0; i < col && obstacleGrid[0][i] == 0; i++) {
            dp[0][i] = 1;
        }

        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (obstacleGrid[i][j] == 1) {      // 如果遇见障碍物就设置路径为 0
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
                }
            }
        }
        return dp[row - 1][col - 1];
    }

    /**
     * 动态规划(简化为一行)
     * 如果是原始版本的话，需要先将 第一行、第一列进行初始化，循环遍历也是从第 2 行开始的
     * 而简化版只初始化路第一个元素，循环遍历是从第 1 行开始的
     */
    public static int uniquePathsWithObstacles_2(int[][] obstacleGrid) {
        int n = obstacleGrid.length;
        int m = obstacleGrid[0].length;
        int[] f = new int[m];

        f[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (obstacleGrid[i][j] == 1) {
                    f[j] = 0;
                    continue;
                }
                // j-1 是由于从 0 开始循环，故此进行判断出界
                // obstacleGrid[i][j - 1] == 0 判断该位置的前一个位置是否正常，如果正常就相加，如果不正常就还是原来的值(该位置的上面位置的值)
                if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {
                    f[j] += f[j - 1];
                }
            }
        }

        return f[m - 1];
    }
}
